package dp;

/**
 * 买卖股票的最佳时机 II
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */
public class P122 {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] dp = new int[len];
        dp[0] = 0;
        dp[1] = prices[1] - prices[0];
        if (dp[1] < 0) {
            dp[1] = 0;
        }
        // 装填dp数组
        for (int i = 2; i < len; i++) {
            int maxPro = dp[i - 1];
            for (int j = 0; j <= i - 1; j++) { // 新的买入点
                if ((prices[i] - prices[j]) > 0) {
                    int profit = (j - 1 >= 0 ? dp[j - 1] : 0) + prices[i] - prices[j];
                    if (profit > maxPro) {
                        maxPro = profit;
                    }
                }
            }
            dp[i] = maxPro;
        }
        return dp[len - 1];
    }

    public static void main(String[] args) {
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        System.out.println(new P122().maxProfit(prices));
    }
}
